package com.leet.code.lcof;

import java.util.LinkedList;
import java.util.List;

public class Code41 {

    public static void main(String[] args) {

        MedianFinder medianFinder = new MedianFinder();

        medianFinder.addNum(-1);
        medianFinder.addNum(-2);
        medianFinder.addNum(-3);
        medianFinder.addNum(-4);
        medianFinder.addNum(-5);

        for (int i : medianFinder.list) {
            System.out.println(i);
        }

        System.out.println(medianFinder.findMedian());


    }

    public static class MedianFinder {

        List<Integer> list;

        public MedianFinder() {
            list = new LinkedList<>();
        }

        public void addNum(int num) {
            if (list.size() == 0) {
                list.add(num);
            } else {
                list.add(search(num), num);
            }
        }

        public double findMedian() {
            if (list.size() == 0) {
                return 0;
            }

            int i = list.size() >>> 1;
            if ((list.size() & 1) == 1) {
                return (double) list.get(i);
            } else {
                return ((double) (list.get(i) + list.get(i - 1))) / 2;
            }
        }


        public int search(int num) {
            int s = 0, e = list.size() - 1;
            int m = (s + e) >>> 1;
            while (s < e) {
                if (list.get(m) == num) {
                    return m;
                } else if (list.get(m) > num) {
                    e = m - 1;
                    if (e == -1) {
                        e = 0;
                    }
                } else {
                    s = m + 1;
                }
                m = (s + e) >>> 1;
            }


            if (list.get(m) > num) {
                return m;
            } else {
                return m + 1;
            }

        }


    }


}
